package com.itheima.leetcode;

/**
 * 合并多个有序链表
 *
 * @FileName E01LeetCode23
 * @Description
 * @Author Sword
 * @date 2025-05-22
 **/
public class E01LeetCode23 {

    public static ListNode mergeKLists(ListNode[] lists) {
        MinHeap queue = new MinHeap(lists.length);

        // 1. 将链表的头结点加入小顶堆

        for (ListNode head : lists) {
            if (head != null) {
                queue.offer(head);
            }
        }

        // 2. 不断从堆顶移除最小元素，加入新链表
        ListNode s = new ListNode(-1, null);
        ListNode p = s;
        while (!queue.isEmpty()) {
            ListNode node = queue.poll();
            p.next = node;
            p = node;
            if (node.next != null) {
                queue.offer(node.next);
            }
        }
        return s.next;
    }


    public static void main(String[] args) {
        /*ListNode[] lists = {com.itheima.leetcode.ListNode.of(1, 4, 5),
                com.itheima.leetcode.ListNode.of(1, 3, 4),
                com.itheima.leetcode.ListNode.of(2, 6),
                null
        };*/

        ListNode[] lists = {com.itheima.leetcode.ListNode.of(1),
                com.itheima.leetcode.ListNode.of(0)
        };
        ListNode listNode = mergeKLists(lists);
        System.out.println(listNode);
    }

}
